import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-27
 * Time: 23:17
 */
public class Solution {
    //DP
    public int coinChange(int[] coins, int amount) {
        int max=amount+1;
        //数组的下标表示总金额,值表示该总金额对应的最小硬币数
        int[] dp=new int[max];
        //初始化为amount+1,为了后面能分辨出是否能组成该总金额
        Arrays.fill(dp,max);
        dp[0]=0;//总金额为零就不需要硬币
        for(int i=1;i<=amount;i++){
            //dp[i]=Min(dp[i-一个硬币的金额])+1
            //因为硬币有不同的金额,所以要循环遍历找到最小硬币数
            for(int j=0;j<coins.length;j++){
                if(i>=coins[j]){
                    dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        //如果不能组成返回-1
        return dp[amount]==max?-1:dp[amount];
    }
}
